﻿// QuadTree.cs
//
// Author: Luoyingliang
// Email: 731984870@qq.com
// 
// Copyright (c) 2018 Team Acoris
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
using System;
using System.Collections.Generic;
using System.Text;

namespace Acoris.Foundation
{
    using System.Numerics;

    /// <summary>
    /// represents a quad tree node
    /// </summary>
    /// <typeparam name="TElement">element type</typeparam>
    public sealed class QuadTreeNode<TElement>
    {
        public const int MaxSize = 256;
        /// <summary>
        /// 
        /// </summary>
        private QuadTreeNode() { }

        internal QuadTreeNode<TElement>[] nodes = new QuadTreeNode<TElement>[4];

        internal QuadTreeNode<TElement> NW {
            get { return nodes[0]; }
            set { nodes[0] = value; }
        }

        internal QuadTreeNode<TElement> NE {
            get { return nodes[1]; }
            set { nodes[1] = value; }
        }

        internal QuadTreeNode<TElement> SW {
            get { return nodes[2]; }
            set { nodes[2] = value; }
        }

        internal QuadTreeNode<TElement> SE {
            get { return nodes[3]; }
            set { nodes[3] = value; }
        }

        internal Vector2           position;
        internal Vector2           size;
        internal IList<TElement>   element;

        public static QuadTreeNode<TElement> CreateNode(Vector2 position, Vector2 size) {
            return new QuadTreeNode<TElement>
            {
                position = position,
                size = size,
                element = new List<TElement>()
            };
        }
    }

    /// <summary>
    /// represents a enumeration which indicate node position
    /// </summary>
    public enum SubNodePosition : byte
    {
        NW = 0,
        NE = 1,
        SW = 2,
        SE = 3,
        OutOfPosition
    }

    /// <summary>
    /// represents a quad tree node extension
    /// </summary>
    public static class QuadTreeNodeExtension
    {
        //-----------------
        //|  00   |   01  |
        //|  NW   |   NE  |
        //|----------------
        //|  10   |   11  |
        //|  SW   |   SE  |
        //-----------------

        /// <summary>
        /// 
        /// </summary>
        /// <typeparam name="TElement">element type</typeparam>
        /// <param name="node"></param>
        /// <param name="position"></param>
        /// <returns></returns>
        public static SubNodePosition GetPosition<TElement>(this QuadTreeNode<TElement> node, Vector2 position) {
            var halfWidth = node.size.X;
            var halfHeight = node.size.Y;
            var x = node.position.X;
            var y = node.position.Y;

            var lowBit =  (position.X >= x && position.X <= (halfWidth + x))? 1 : 0;
            var highBit = (position.Y>= y && position.Y <= (halfHeight + y))? 1 : 0;

            return (SubNodePosition)((highBit << 1) + lowBit);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <typeparam name="TElement"></typeparam>
        /// <param name="node"></param>
        /// <param name="element"></param>
        public static void AddElement<TElement>(this QuadTreeNode<TElement> node,TElement element) {
            if (node.element.Count < QuadTreeNode<TElement>.MaxSize) {
                node.element.Add(element);
            }
            else {
                
            }
        }

        public static void Split<TElement>(this QuadTreeNode<TElement> node) {

        }
    }

    /// <summary>
    /// represents a quad tree
    /// </summary>
    public sealed class QuadTree<TElement>
    {
        private QuadTreeNode<TElement> root;

        /// <summary>
        /// 
        /// </summary>
        /// <param name="width"></param>
        /// <param name="height"></param>
        public QuadTree(float width, float height) {
        }
        
    }

}
